인공지능 개념 (PolyU COMP5511) 3강에 오신 것을 환영합니다. 인공지능 개념 (PolyU COMP5511). 이번 시간에는 단일 에이전트 경로 탐색에서 적대적 탐색으로 전환하며, 에이전트는 경쟁적인 다중 에이전트 환경에서 작동합니다. 또한 제약 만족 문제(CSP)를 소개합니다. 이는 경로보다는 특정 제약 조건을 만족하는 상태를 찾는 것을 목표로 하는 패러다임입니다.

핵심 개념

• 적대적 탐색: 는 다음과 같은 알고리즘에 중점을 둡니다. 미니맥스 및 알파-베타 가지치기를 사용하여 지능적인 상대방에 대해 합리적인 결정을 내립니다.
• 몬테카를로 트리 탐색 (MCTS): 는 확률적 의사 결정 탐색으로, 알파고와 같은 현대 게임 AI의 기반이 됩니다.
• 제약 만족: 는 변수, 도메인 및 제약 조건을 사용하여 문제를 모델링하며, 백트래킹 및 지역 탐색와 같은 현대 게임 AI의 기반이 됩니다.

복잡도 분석

적대적 설정에서 탐색 공간 복잡도는 종종 게임 분기 계수 $b$ 와 깊이 $d$로 정의되며, 이는 계산 비용으로 이어집니다: $$O(b^d)$$ 이러한 지수적 성장은 알파-베타 가지치기와 같은 효율적인 가지치기 전략을 필요로 합니다.